#include <iostream>
#include <vector>
using namespace std;
// 实现高精度数加上低精度数(逆序)
vector<int> add(const vector<int>& A, const vector<int>& B) {
    vector<int> C;
    int f = 0;
    for(int i = 0; i < A.size() || i < B.size(); i++) {
        int a = i < A.size() ? A[i] : 0;
        int b = i < B.size() ? B[i] : 0;
        int t = a + b + f;
        C.push_back(t % 10);
        f = t / 10;
    }
    if(f) {
        C.push_back(f);
    }
    return C;
}
// 实现高精度数减去一个低精度数（逆序）
vector<int> sub(vector<int> a, int b) {
    int i = 0;
    while (b > 0) {
        if (i < a.size()) {
            a[i] -= b % 10;
            if (a[i] < 0) {
                a[i] += 10;
                b = b / 10 + 1; // 借位
            } else {
                b /= 10;
            }
        } else {
            // b 比 a 大，不支持负数结果
            throw runtime_error("Result would be negative!");
        }
        i++;
    }

    // 去掉前导 0
    while (a.size() > 1 && a.back() == 0)
        a.pop_back();
    return a;
}
// 实现高精度乘以高精度（逆序）
vector<int> mulpromax(vector<int>& a, vector<int>& b) {
    int n = a.size(), m = b.size();
    vector<int> temp(n + m + 10, 0);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            temp[i + j] += a[i] * b[j];
            temp[i + j + 1] += temp[i + j] / 10;
            temp[i + j] %= 10; 
        }
    }
    
    while(temp.back() == 0 && temp.size() > 1) {
        temp.pop_back();
    }
    return temp;
}

// 实现高精度数乘以低精度数（逆序）
vector<int> mulpro(vector<int>& a, int b) {
    int n = a.size();
    vector<int> temp(n + 1, 0);
    for (int i = 0; i < n; i++) {
        temp[i] += a[i] * b;
        temp[i + 1] += temp[i] / 10;
        temp[i] %= 10;
    }
    // 去掉前导0（最高位）
    while (temp.size() > 1 && temp.back() == 0) {
        temp.pop_back();
    }
    return temp;
}
// 实现高精度数除以低精度数(原来的顺序进，原来的顺序出来)
vector<int> div(const vector<int>& a, int b) {
    if(b == 0) {
        perror("fucking fuck");
    }
    vector<int> ret;
    int der = 0;
    for(auto s : a) {
        int temp = der * 10 + s;
        ret.push_back(temp / b);
        der = temp % b;
    }
    while(ret.size() > 0 && ret.front() == 0) {
        ret.erase(ret.begin());
    }
    if(ret.empty()) {
        ret.push_back(0);
    }
    return ret;
}
// 实现高精度数除以高精度数(返回的是商和余数)
pair<vector<int>, vector<int>> divide(const vector<int>& a, const vector<int>& b) {
    int n = a.size(), m = b.size();
    vector<int> quotient(n, 0);   // 商
    vector<int> remainder = a;    // 余数

    // 长除法的核心过程
    for (int i = n - 1; i >= m - 1; i--) {
        // 将当前余数与新的被除数位数结合
        int quotient_digit = 0;
        while (true) {
            bool can_subtract = true;
            // 使用除数乘以商的当前位并与余数进行比较
            for (int j = 0; j < m; j++) {
                if (remainder[i - m + 1 + j] < b[j] * (quotient_digit + 1)) {
                    can_subtract = false;
                    break;
                }
            }

            // 判断是否能减去，决定商的当前位
            if (can_subtract) {
                quotient_digit++;
            } else {
                break;
            }
        }

        // 更新余数
        for (int j = 0; j < m; j++) {
            remainder[i - m + 1 + j] -= b[j] * quotient_digit;
        }

        // 处理余数中的进位
        for (int j = i; j >= 0; j--) {
            if (remainder[j] < 0) {
                remainder[j] += 10;
                remainder[j - 1]--;
            }
        }
        
        // 保存商
        quotient[i - m + 1] = quotient_digit;
    }

    // 移除商和余数中的前导零
    while (quotient.size() > 1 && quotient.back() == 0) {
        quotient.pop_back();
    }
    while (remainder.size() > 1 && remainder.back() == 0) {
        remainder.pop_back();
    }

    return {quotient, remainder};
}
int main() 
{

}